package leetcode.editor.cn;

import java.util.LinkedList;
import java.util.List;

public class Solution95 {
    public List<TreeNode> generateTrees(int n) {
        if (n == 0) return new LinkedList<>();
        return helper(1, n);
    }

    List<TreeNode> helper(int lo, int hi){
        List<TreeNode> res = new LinkedList<>();
        if (lo>hi){
            res.add(null);
            return res;
        }
        for (int i=lo; i<=hi; i++){
            List<TreeNode> leftNode = helper(lo, i-1);
            List<TreeNode> rightNode = helper(i+1, hi);
            for (TreeNode left : leftNode){
                for (TreeNode right : rightNode){
                    TreeNode root = new TreeNode(i);
                    root.left = left;
                    root.right = right;
                    res.add(root);
                }
            }
        }
        return res;
    }
}
